package zuochengyun.chapter8;

//未排序数组中累加和小雨或等于给定值的最长子数组长度
public class UnSortedArrayNoExceedK {

	public int maxlength(int[] arr, int k){
		//sumArr的左侧最大值数组
		//比如arr : [1, 2, -1, 5, -2]
		//sumArr : [0, 1, 3, 2, 7, 5]
		//sum第一个数为0表示没有任何一个数时累加和为0
		//help: [0, 1, 3, 3, 7, 7]
		int[] help = new int[arr.length + 1];
		int sum = 0;
		help[0] = sum;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			help[i + 1] = Math.max(sum, help[i]);
		}
		
		//help是有序的，所以我么能够对其进行二分查找，找到大于某一个值出现的最早位置
		sum = 0;
		int res = 0;
		int pre = 0;
		int len = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			pre = getLessIndex(help, sum - k);
			len = pre == -1 ? 0 : i - pre + 1;
			res = Math.max(len, res);
		}
		return res;
	}

	//找到大于等于num出现的最早位置
	private int getLessIndex(int[] help, int num) {
		int low = 0;
		int high = help.length - 1;
		int middle = 0;
		int res = -1;
		while(low <= high){
			middle = low + (high - middle) / 2;
			if(help[middle] >= num){
				high = middle - 1;
				res = middle;
			}else{
				low = middle + 1;
			}
		}
		return res;
	}
	
	//求小于等于k的最大和
	public int maxSum(int[] arr, int k){
		//sumArr的左侧最大值数组
		//比如arr : [1, 2, -1, 5, -2]
		//sumArr : [0, 1, 3, 2, 7, 5]
		//sum第一个数为0表示没有任何一个数时累加和为0
		//help: [0, 1, 3, 3, 7, 7]
//		int[] sum = new int[arr.length];
//		sum[0] = arr[0];
//		for (int i = 1; i < arr.length; i++) {
//			sum[i] =  sum[i - 1] + arr[i];
//		}
//		
//		int res = 0;
//		int pre = 0;
//		int len = 0;
//		int curSum = 0;
//		for (int i = 0; i < arr.length; i++) {
//			curSum += arr[i];
//			pre = getLessNumIndex(sum, curSum - k);
//			len = pre == -1 ? 0 : i - pre + 1;
//			res = Math.max(len, res);
//		}
//		return res;
		int res = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			int curSum = 0;
			for (int j = i; j < arr.length; j++) {
				curSum += arr[j];
				if(curSum <= k){
					res = Math.max(curSum, res);
				}
			}
		}
		return res;
	}

	//找到最小的大于等于num的下标
	private int getLessNumIndex(int[] sum, int num) {
		return 0;
	}
}
